#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <Windows.h>

#define MAX_WORD_SIZE 30
#define MAX_MEANING_SIZE 30
#define PRINT_SIZE 1000
#define MAX_ELEMENT 3000
#define INSERT_WORD 1
#define DELETE_WORD 2
#define DISPLAY 3
#define WORD_SEARCH 4
#define DATE_WORD_DISPLAY 5
#define MIN_COUNT_DISPLAY 6
#define MAX_COUNT_DISPLAY 7
#define GAME_PLAY 8
#define EXIT 9

enum COLOR {RED,BLACK};
typedef enum COLOR COLOR;
typedef struct	DATA{
	int date;
	char word[MAX_WORD_SIZE];
	char meaning[MAX_MEANING_SIZE];
	int count;
}DATA;

typedef struct Heaptype{
	DATA heap[MAX_ELEMENT];
	int heap_size;
}Heaptype;

typedef struct rbtree{
	DATA 			key;
	COLOR			color;
	struct rbtree 	*left;
	struct rbtree 	*right;
	struct rbtree	*p;
}ELEM_RB;
typedef ELEM_RB 		*RBTREE;

//전역변수
RBTREE nil;// nil 노드를 따로 만드는 이유는 BLACK 속성을 가지기 때문이다.
DATA NULL_DATA; // ;
int print_count;
int game_num = 0;

//함수
RBTREE left_rotate(RBTREE tree, RBTREE base);// 좌회전 함수
RBTREE right_rotate(RBTREE tree, RBTREE base);// 우회전 함수
RBTREE RB_insert_fixup(RBTREE tree, RBTREE input);//삽입 픽업함수
RBTREE RB_insertword(RBTREE tree, RBTREE input);// 삽입 함수(검색을 위해)
RBTREE RB_insertfre(RBTREE tree,RBTREE input);//빈도수를 위해
RBTREE RB_insertdate(RBTREE tree,RBTREE input);//입력한 순서를 위해
RBTREE make_node(DATA input);// 노드 생성 함수
RBTREE make_nil(); // nil 노드 생성 함수
RBTREE tree_minimum(RBTREE root); ;
RBTREE tree_successor(RBTREE root);
RBTREE RB_delete_fixup(RBTREE tree, RBTREE put);
RBTREE RB_delete(RBTREE tree, RBTREE put);
RBTREE tree_searchword(RBTREE tree, DATA d);
RBTREE tree_searchdate(RBTREE tree, int d);
void print_inorder(RBTREE tree,RBTREE entree);
void delete_all(RBTREE tree);
void emptydata(DATA a);
void print_inorder_end(RBTREE tree, FILE *f);
void print_inorderdate(RBTREE tree,RBTREE entree, int date);
void print_inorder_word(RBTREE tree,DATA mindata,DATA maxdata);
void insert_max_heap(Heaptype *h,DATA item);
void insert_min_heap(Heaptype *h,DATA item);
DATA delete_max_heap(Heaptype *h);
DATA delete_min_heap(Heaptype *h);
void display(RBTREE tree);
void insert_value(RBTREE tree,Heaptype *minheap,Heaptype *maxheap);
void heap_init(Heaptype *minheap,Heaptype *maxheap);
void insert_game_array(RBTREE tree,DATA *d);

int main(void)
{
	FILE	*engfile = fopen("eng1.txt","r");
	//구조체 선언
	Heaptype minheap,maxheap;
	RBTREE englishtree;
	RBTREE frequencytree;
	RBTREE datetree;
	RBTREE val;
	DATA temp,temp1,temp2;
	DATA game[MAX_ELEMENT];
	//변수 선언
	int date;
	int num = 0;
	int year,month,day;
	int choice = 0;
	int tempn;
	int life = 0;
	//initializing

	time_t timer;
	struct tm *t;
	//초기화

	minheap.heap_size = 0;
	maxheap.heap_size = 0;
	emptydata(NULL_DATA);
	nil = make_nil();
	englishtree = nil;
	frequencytree = nil;
	datetree = nil;

	timer = time(NULL); // 현재 시각을 초 단위로 얻기
	t = localtime(&timer); // 초 단위의 시간을 분리하여 구조체에 넣기
	date = ((t->tm_year-100) * 10000000 ) + ((t->tm_mon+1) * 100000) + (t->tm_mday * 1000);  	

	while(feof(engfile)==0){

		fscanf(engfile,"%d %s %s %d ",&temp1.date,&temp1.word,&temp1.meaning,&temp1.count);
		if((date <= temp1.date) &&(temp1.date < (date + 1000)))num++; // 현재 날짜
		val = make_node(temp1);      //노드를 만들고
		englishtree = RB_insertword(englishtree,val);//트리에 넣고
		//	val = make_node(temp1);
		//frequencytree = RB_insertfre(frequencytree,val);
		val = make_node(temp1);
		datetree = RB_insertdate(datetree,val);
		insert_max_heap(&maxheap,temp1);
		insert_min_heap(&minheap,temp1);

	}

	fclose(engfile);

	/*print_count = 15;
	print_inorder(frequencytree,englishtree);
	printf("아무키나 눌러주세요 메뉴화면으로 넘어갑니다.\n");*/

	printf("오늘의 암기단어\n");
	for(tempn = 0; tempn < 15;tempn++){

		temp2 = delete_min_heap(&minheap);
		printf("단어:%s 뜻:%s 빈도수:%d\n",temp2.word,temp2.meaning,temp2.count);
		tree_searchword(englishtree,temp2)->key.count++;
	}
	heap_init(&minheap,&maxheap);
	insert_value(englishtree,&minheap,&maxheap);
	printf("아무키나 눌러주세요 메뉴화면으로 넘어갑니다.\n");
	getchar();
	system("cls");

	do{	
		printf("┌─────────┐\n");
		printf("│1.단어 입력       │\n");
		printf("│2.단어 삭제       │\n");
		printf("│3.전체 출력       │\n");
		printf("│4.단어 찾기       │\n");
		printf("│5.입력 날짜 단어  │\n");
		printf("│6.빈도수 낮은 단어│\n");
		printf("│7.빈도수 높은 단어│\n");
		printf("│8.단어 게임       │\n");
		printf("│9.종료            │\n");
		printf("└─────────┘\n");
		printf("\n>");
		scanf("%d",&choice);

		switch(choice){

		case INSERT_WORD:		

			num += date;
			temp.date = num;
			printf("\n단어를 입력합니다.\n");
			scanf("%s",temp.word);
			printf("\n뜻을 입력합니다.\n");
			scanf("%s",temp.meaning);
			temp.count = 0;

			printf("input: %s\n", temp.word);
			val = make_node(temp);      //노드를 만들고
			englishtree = RB_insertword(englishtree,val);//트리에 넣고
			//val = make_node(temp);
			//frequencytree = RB_insertfre(frequencytree,val);
			val = make_node(temp);
			datetree = RB_insertdate(datetree,val);
			//	print_inorder(englishtree);    //출력
			insert_min_heap(&minheap,temp);
			insert_max_heap(&maxheap,temp);

			printf("\n");
			num -= date; // 오늘 날짜를 뺌
			num++;//단어 하나 추가 했으니 ++

			break;

		case DELETE_WORD:	

			printf("\n단어를 입력합니다.\n");
			scanf("%s",temp.word);
			val = tree_searchword(englishtree,temp); //노드를 찾아보고

			if(val != nil)
			{
				printf("delete: %s\n", temp.word);
				englishtree = RB_delete(englishtree,val); //있을때 트리에서 지우고
				//	print_inorder(englishtree);      // 출력
				printf("\n");
				heap_init(&minheap,&maxheap);
				insert_value(englishtree,&minheap,&maxheap);break;

			}else{
				printf("'%s' is not exist in tree \n", temp.word);
			}
			break;

		case DISPLAY://전체 출력
			display(englishtree);break;

		case WORD_SEARCH://단어 검색

			printf("\n단어를 입력합니다.\n");
			scanf("%s",temp.word);
			val = tree_searchword(englishtree,temp);
			if(val != nil){

				printf("뜻은 %s 입니다.\n",val->key.meaning);
				val->key.count++;
			
			}else{

				printf("%s 가 존재하지 않습니다.\n",temp.word);
				int n = strlen(temp.word);
				DATA maxdata = temp;
				maxdata.word[n] = '{';
				maxdata.word[n+1] = NULL;
				printf("[[[[관련 단어]]]]\n");
				print_inorder_word(englishtree,temp,maxdata);
			}
			break;

		case DATE_WORD_DISPLAY://년도 출력

			printf("출력하고 싶은 날짜를 입력하시오.\n");
			printf("년도(20__)? ");scanf("%d",&year);
			printf("__월? ");scanf("%d",&month);
			printf("__일? ");scanf("%d",&day);
			date = (year * 10000000 ) + (month * 100000) + (day*1000);
			print_inorderdate(datetree,englishtree,date);
			break;

			//case 6://빈도수 출력(트리이용)
			//	print_count = 15;
			//	print_inorder(frequencytree,englishtree);break;

		case MIN_COUNT_DISPLAY: //최저

			for(tempn = 0; tempn < 15;tempn++){
				temp2 = delete_min_heap(&minheap);
				printf("단어:%s 뜻:%s 빈도수:%d\n",temp2.word,temp2.meaning,temp2.count);
				tree_searchword(englishtree,temp2)->key.count++;
			}
			heap_init(&minheap,&maxheap);

			insert_value(englishtree,&minheap,&maxheap);
			break;

		case MAX_COUNT_DISPLAY: //최대

			for(tempn = 0; tempn < 15;tempn++){
				temp2 = delete_max_heap(&maxheap);
				printf("단어:%s 뜻:%s 빈도수:%d\n",temp2.word,temp2.meaning,temp2.count);
				tree_searchword(englishtree,temp2)->key.count++;
			}

			heap_init(&minheap,&maxheap);
			insert_value(englishtree,&minheap,&maxheap);
			break;

		case GAME_PLAY:

			srand((unsigned int)time(NULL));
			life = 100;
			game_num = 0;
			insert_game_array(englishtree, game);

			do{
				temp = game[rand()%(game_num)];
				printf("뜻: %s 에 해당하는 단어를 입력하시오.(종료는 0을 입력하세요)\n",temp.meaning);
				scanf("%s",temp1.word);

				if(temp1.word[0] == '0'){ //종료
					printf("게임을 종료합니다.\n");
					break;
				}

				if(strcmp(temp.word,temp1.word) == 0){
					printf("정답입니다.(life:%d)\n",life);
				}else{
					life -= 10;
					printf("오답입니다.(life:%d)\n",life);
					printf("정답 : %s \n",temp.word);
				}
				if(life <= 0)break;

			}while(1);

			break;

		case EXIT://종료

			break;

		}

		if(choice != 9){

			printf("아무키나 눌러주세요 다음 작업으로 넘어갑니다.\n");
			getchar();getchar();
			system("cls");
		}

		engfile = fopen("eng1.txt","w");
		print_inorder_end(englishtree,engfile);
		fclose(engfile);

	}
	while (choice != 9);

	// 동적 할당 모두 헤제
	delete_all(englishtree);
	delete_all(frequencytree);
	delete_all(datetree);
	free(nil);

	return 0;
}

void emptydata(DATA a){

	a.count = 0;
	a.date = 0;
	a.word[0] = NULL;
	a.meaning[0] = NULL;
}

RBTREE left_rotate(RBTREE tree, RBTREE base){

	RBTREE y = base -> right;
	base -> right = y -> left;

	if (y -> left != nil)
		y -> left -> p = base;

	y -> p = base -> p;

	if (base -> p == nil){
		tree = y;
	}
	else if (base == base -> p -> left){
		base -> p -> left = y;
	}
	else{
		base -> p -> right = y;
	}

	y -> left = base;
	base -> p = y;

	return tree;
}

RBTREE right_rotate(RBTREE tree, RBTREE base){// 우회전 함수

	RBTREE y = base -> left;
	base -> left = y -> right;

	if (y -> right != nil)
		y -> right -> p = base;

	y ->p = base -> p;

	if (base -> p == nil){
		tree = y;
	}
	else if (base == base -> p -> right){
		base -> p -> right = y;
	}
	else{
		base -> p -> left = y;
	}

	y -> right = base;
	base -> p = y;

	return tree;
}

RBTREE RB_insert_fixup(RBTREE tree, RBTREE input){

	RBTREE y;

	while ( input -> p -> color == RED)
	{
		if( (input -> p) == (input -> p -> p -> left))
		{
			y = input -> p -> p -> right;
			if (y -> color == RED)
			{
				input -> p -> color = BLACK;
				y -> color = BLACK;
				input -> p -> p -> color = RED;
				input = input -> p -> p;
			}
			else 
			{
				if ( input == input -> p -> right)
				{
					input = input -> p;
					tree = left_rotate(tree,input);
				}
				input -> p -> color = BLACK;
				input -> p -> p -> color = RED;
				tree = right_rotate(tree,input->p->p);
			}
		}
		else
		{
			y = input -> p -> p -> left;
			if (y -> color == RED)
			{
				input -> p -> color = BLACK;
				y -> color = BLACK;
				input -> p -> p -> color = RED;
				input = input -> p -> p;
			}
			else 
			{
				if ( input == input -> p -> left)
				{
					input = input -> p;
					tree = right_rotate(tree,input);
				}
				input -> p -> color = BLACK;
				input -> p -> p -> color = RED;
				tree = left_rotate(tree,input->p->p);
			}
		}
	}

	tree -> color = BLACK;

	return tree;
}

RBTREE RB_insertword(RBTREE tree, RBTREE input){// 삽입 함수

	RBTREE y = nil;
	RBTREE x = tree;

	while (x != nil)
	{
		y = x;
		if (strcmp((input -> key.word), (x -> key.word)) < 0){
			x = x -> left;
		}
		else{
			x = x -> right;
		}
	}
	input -> p = y;

	if (y == nil){
		tree = input;
	}
	else if ((strcmp((input -> key.word), (y -> key.word)) < 0)){
		y -> left = input;
	}
	else{
		y -> right = input;
	}

	input -> left = nil;
	input -> right = nil;
	input -> color = RED;

	return RB_insert_fixup(tree,input);
}

RBTREE RB_insertfre(RBTREE tree, RBTREE input){// 삽입 함수

	RBTREE y = nil;
	RBTREE x = tree;

	while (x != nil)
	{
		y = x;
		if ((input->key.count) < (x->key.count)){
			x = x -> left;
		}
		else{
			x = x -> right;
		}
	}
	input -> p = y;

	if (y == nil){
		tree = input;
	}
	else if ((input->key.count) < (y->key.count)){
		y -> left = input;
	}
	else{
		y -> right = input;
	}

	input -> left = nil;
	input -> right = nil;
	input -> color = RED;

	return RB_insert_fixup(tree,input);
}

RBTREE RB_insertdate(RBTREE tree, RBTREE input){// 삽입 함수

	RBTREE y = nil;
	RBTREE x = tree;

	while (x != nil)
	{
		y = x;
		if ((input->key.date) < (x->key.date)){
			x = x -> left;
		}
		else{
			x = x -> right;
		}
	}
	input -> p = y;

	if (y == nil){
		tree = input;
	}
	else if ((input->key.date) < (y->key.date)){
		y -> left = input;
	}
	else{
		y -> right = input;
	}

	input -> left = nil;
	input -> right = nil;
	input -> color = RED;

	return RB_insert_fixup(tree,input);
}

RBTREE make_node(DATA input){

	RBTREE tmp;

	tmp =  (RBTREE)malloc(sizeof(ELEM_RB));
	tmp ->key = input;
	tmp ->left = nil;
	tmp -> right = nil;
	tmp ->p = nil;

	return tmp;
}

RBTREE make_nil() // nil 노드 생성 함수
{
	RBTREE tmp;

	tmp = (RBTREE)malloc(sizeof(ELEM_RB));
	tmp ->key = NULL_DATA;
	tmp ->left = NULL;
	tmp -> right = NULL;
	tmp ->p = NULL;
	tmp ->color = BLACK;

	return tmp;
}

RBTREE tree_minimum(RBTREE root){

	RBTREE tmp = root;

	while (tmp -> left != nil)
	{
		tmp = tmp -> left;
	}

	return tmp;
}

RBTREE tree_successor(RBTREE root){

	RBTREE tmp;

	if (root -> right != nil)
		return tree_minimum(root -> right);

	tmp = root->p;

	while((tmp != nil) && (root == tmp->right))
	{
		root = tmp;
		tmp = tmp -> p;
	}

	return tmp;
}

RBTREE RB_delete_fixup(RBTREE tree, RBTREE put){

	RBTREE w;

	while((put != tree) &&(put -> color == BLACK))
	{
		if(put == put -> p -> left)
		{
			w = put -> p -> right;
			if (w -> color == RED)
			{
				w -> color = BLACK;
				put -> p -> color = RED;
				tree = left_rotate(tree,put->p);
				w = put -> p -> right;
			}
			if ((w->left->color == BLACK)&&(w->right->color == BLACK))
			{
				w -> color = RED;
				put = put -> p;
			}
			else 
			{
				if(w -> right -> color == BLACK)
				{
					w->left->color = BLACK;
					w-> color = RED;
					tree = right_rotate(tree,w);
					w = put->p->right;
				}
				w -> color = put -> p -> color;
				put -> p -> color = BLACK;
				w -> right -> color = BLACK;
				tree = left_rotate(tree,put->p);
				put = tree;
			}
		}
		else
		{
			w = put -> p -> left;
			if (w -> color == RED)
			{
				w -> color = BLACK;
				put -> p -> color = RED;
				tree = right_rotate(tree,put->p);
				w = put -> p -> left;
			}
			if ((w->right->color == BLACK)&&(w->left->color == BLACK))
			{
				w -> color = RED;
				put = put -> p;
			}
			else 
			{
				if(w -> left -> color == BLACK)
				{
					w->right->color = BLACK;
					w-> color = RED;
					tree = left_rotate(tree,w);
					w = put->p->left;
				}
				w -> color = put -> p -> color;
				put -> p -> color = BLACK;
				w -> left -> color = BLACK;
				tree = right_rotate(tree,put->p);
				put = tree;
			}
		}
	}

	put -> color = BLACK;

	return tree;
}

RBTREE RB_delete(RBTREE tree, RBTREE put){

	RBTREE y;
	RBTREE x;

	if ((put -> left == nil)||(put->right == nil)){
		y = put;
	}
	else{
		y = tree_successor(put);
	}
	if(put -> left != nil){
		x = y -> left;
	}
	else{
		x = y -> right;
	}

	x->p = y->p;

	if (y -> p == nil){
		tree = x;
	}
	else 
	{
		if (y == y -> p -> left){
			y -> p -> left = x;
		}
		else{
			y -> p -> right = x;
		}
	}
	if ( y != put){
		put -> key = y -> key;
	}
	if (y -> color == BLACK){
		tree = RB_delete_fixup(tree,x);
	}

	return tree;
}

RBTREE tree_searchword(RBTREE tree, DATA d){

	RBTREE root;
	root = tree;

	while ((root != nil) && (strcmp(d.word, root -> key.word) != 0))
	{
		if (strcmp(d.word, root -> key.word) == -1){
			root = root -> left;
		}
		else{
			root = root -> right;
		}
	}
	return root;
}

RBTREE tree_searchdate(RBTREE tree, int d){

	RBTREE root;
	root = tree;

	while ((root != nil) && d != root -> key.date )
	{
		if (d < root -> key.date){
			root = root -> left;
		}
		else{
			root = root -> right;
		}
	}
	return root;
}

void insert_game_array(RBTREE tree,DATA *d){

	if(tree != nil)
	{	
		insert_game_array(tree->left, d);

		d[game_num++] = tree->key;

		insert_game_array(tree->right, d);
	}
}

void insert_value(RBTREE tree,Heaptype *minheap,Heaptype *maxheap){

	if(tree != nil)
	{	
		insert_value(tree->left, minheap,maxheap);

		insert_min_heap(minheap,tree->key);
		insert_max_heap(maxheap,tree->key);

		insert_value(tree->right, minheap,maxheap);
	}
}

void display(RBTREE tree){// INORDER 로 탐색하면서 깊이만큼 출력

	if(tree != nil)
	{	
		display(tree->left);

		printf("단어:%s ",tree->key.word);
		printf("뜻:%s",tree->key.meaning);
		printf("단어 검색 횟수: %d\n",tree->key.count);
		tree->key.count++;

		display(tree->right);
	}
}

void print_inorder(RBTREE tree,RBTREE entree){// INORDER 로 탐색하면서 깊이만큼 출력

	DATA temp0;	

	if(tree != nil)
	{	
		print_inorder(tree->left,entree);

		if(print_count <= 0)return;
		print_count--;

		printf("단어:%s ",tree->key.word);
		printf("뜻:%s ",tree->key.meaning);
		printf("단어 검색 횟수: %d\n",tree->key.count);

		tree->key.count++;
		strcpy(temp0.word,tree->key.word);
		tree_searchword(entree,temp0)->key.count++;

		print_inorder(tree->right,entree);
	}
}

void print_inorder_word(RBTREE tree,DATA mindata,DATA maxdata){

	if(tree != nil)
	{	
		print_inorder_word(tree->left,mindata,maxdata);

		if((strcmp(tree->key.word,mindata.word) > 0)&&(strcmp(tree->key.word,maxdata.word) < 0)){
			printf("단어:%s ",tree->key.word);
			printf("뜻:%s",tree->key.meaning);
			printf("단어 검색 횟수: %d\n",tree->key.count);
		}

		print_inorder_word(tree->right,mindata,maxdata);
	}
}

void print_inorderdate(RBTREE tree,RBTREE entree,int date){// INORDER 로 탐색하면서 깊이만큼 출력

	DATA temp0;

	if(tree != nil)
	{	
		print_inorderdate(tree->left,entree, date);

		if((date <= tree->key.date) && (tree->key.date < (date + 1000))){
			printf("no.%d ",tree->key.date - date);
			printf("단어:%s ",tree->key.word);
			printf("뜻:%s\n",tree->key.meaning);
			strcpy(temp0.word,tree->key.word);
			tree_searchword(entree,temp0)->key.count++;
		}

		print_inorderdate(tree->right,entree, date);
	}

}

void print_inorder_end(RBTREE tree,FILE *f){// INORDER 로 탐색하면서 깊이만큼 출력

	if(tree != nil)
	{	
		print_inorder_end(tree->left, f);
		fprintf(f,"%d %s %s %d\n",tree->key.date,tree->key.word,tree->key.meaning,tree->key.count);
		print_inorder_end(tree->right,f);
	}
}

void delete_all(RBTREE tree){

	if(tree != nil)
	{
		delete_all(tree->left);
		delete_all(tree->right);
		free(tree);
	}
}

void insert_max_heap(Heaptype *h,DATA item){

	int i;
	i = ++(h->heap_size);

	while((i != 1)&&(item.count > h->heap[i/2].count)){
		h->heap[i] = h->heap[i/2];
		i /=2;
	}

	h->heap[i] = item;
}

void insert_min_heap(Heaptype *h,DATA item){

	int i;
	i = ++(h->heap_size);

	while((i != 1)&&(item.count< h->heap[i/2].count)){
		h->heap[i] = h->heap[i/2];
		i /=2;
	}

	h->heap[i] = item;
}

DATA delete_max_heap(Heaptype *h){

	int parent, child;
	DATA item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;

	while(child <= h->heap_size){
		if((child < h->heap_size)&&
			(h->heap[child].count) < (h->heap[child+1].count)){
				child++;
		}
		if(temp.count >= h->heap[child].count)break;

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}

	h->heap[parent] = temp;

	return item;
}

DATA delete_min_heap(Heaptype *h){

	int parent, child;
	DATA item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while(child <= h->heap_size){
		if((child < h->heap_size)&&
			(h->heap[child].count) > (h->heap[child+1].count)){
				child++;
		}
		if(temp.count <= h->heap[child].count)break;

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

void heap_init(Heaptype *minheap,Heaptype *maxheap){

	minheap->heap_size = 0;
	maxheap->heap_size = 0;
}